<HTML><HEAD><TITLE>incremental_single_pair_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Length, -SubGraph)</TITLE>
</HEAD><BODY>[ <A HREF="index.html">library(graph_algorithms)</A> | <A HREF="../../index.html">Reference Manual</A> | <A HREF="../../fullindex.html">Alphabetic Index</A> ]
<H1>incremental_single_pair_all_shortest_paths_as_graph(+Graph, +DistanceArg, +SourceNode, +SinkNode, +Modified, -Length, -SubGraph)</H1>
Computes all shortest paths from source to sink in form of a subgraph
<DL>
<DT><EM>Graph</EM></DT>
<DD>a graph structure
</DD>
<DT><EM>DistanceArg</EM></DT>
<DD>which argument of EdgeData to use as distance (integer)
</DD>
<DT><EM>SourceNode</EM></DT>
<DD>source node number (integer)
</DD>
<DT><EM>SinkNode</EM></DT>
<DD>sink node number (integer)
</DD>
<DT><EM>Modified</EM></DT>
<DD>list of e/3 edge structures whose DistanceArg argument has been modified
</DD>
<DT><EM>Length</EM></DT>
<DD>a number (minimum path length)
</DD>
<DT><EM>SubGraph</EM></DT>
<DD>a graph structure
</DD>
</DL>
<H2>Description</H2>
<P>
    Incrementally computes all shortest paths from source node
    SourceNode to sink node SinkNode.  The result is returned in the
    form of a sub-graph of the input graph, which contains all
    relevant edges. If there is no path, the predicate fails.
</P><P>
    DistanceArg refers to the graph's EdgeData information that was
    specified when the graph was constructed. If EdgeData is a simple
    number, then DistanceArg should be 0 and EdgeData will be taken
    as the length of the edge. If EdgeData is a compound data structure,
    DistanceArg should be a number between 1 and the arity of that
    structure and determines which argument of the EdgeData structure
    will be interpreted as the edge's length. Important: the distance
    information in EdgeData must be a non-negative number.
</P><P>
    If DistanceArg is given as -1, then any EdgeData is ignored and
    the length of every edge is assumed to be equal to 1.
</P><P>
    Modified is the list of e/3 edge structures whose DistanceArg
    argument has been modified since the last computation for this
    SourceNode.
</P><P>
    The result is returned in the form of SubGraph, which is a
    sub-graph of the input Graph, containing the same nodes, but only
    those edges that are needed to construct the shortest paths for
    the given parameters.  SubGraph does not inherit the nodename
    information from Graph, this can be set explicitly if required.
</P><P>
    In addition, the Length of the shortest path from source to sink
    is returned.
</P>
<H4>Properties of the resulting SubGraph</H4>
<P>
    To generate an actual path from the resulting SubGraph, start from the
    sink node J, select one of its incoming edges (graph_get_incoming_edges/3)
    to find a predecessor node, and continue this process until the SourceNode
    is reached. Depending on the input graph, the following 2 cases can occur:
    <OL>
    <LI>Graph did not contain zero-length edges: in this case,
    SubGraph is cycle-free and shortest paths can be found by simply 
    selecting arbitrary incoming edges until SourceNode is reached.
    <LI>Graph did contain zero-length edges: in this case, SubGraph
    may contain (zero-length) cycles which one may want to exclude 
    when constructing paths.
    </OL>
    </P>
<H3>Modes and Determinism</H3><UL>
<LI>incremental_single_pair_all_shortest_paths_as_graph(+, +, +, +, +, -, -) is det
</UL>
<H2>Examples</H2>
<PRE>
    ?- sample_graph(G),
       incremental_single_pair_all_shortest_paths_as_graph(G, 0, 1, 5, M, L, E).
    G = graph(13, []([e(1, 6, 1), e(1, 2, 1), e(1, 7, 1)], [], ...)
    L = 2
    SG = graph(13, []([e(1, 6, 1), e(1, 7, 1)], [], ...)
    </PRE>
<H2>See Also</H2>
<A HREF="../../lib/graph_algorithms/possible_path-7.html">possible_path / 7</A>, <A HREF="../../lib/graph_algorithms/shortest_paths-4.html">shortest_paths / 4</A>, <A HREF="../../lib/graph_algorithms/single_pair_shortest_path-5.html">single_pair_shortest_path / 5</A>, <A HREF="../../lib/graph_algorithms/all_short_paths_as_edges-6.html">all_short_paths_as_edges / 6</A>, <A HREF="../../lib/graph_algorithms/all_short_paths_as_graph-6.html">all_short_paths_as_graph / 6</A>, <A HREF="../../lib/graph_algorithms/single_pair_short_path-6.html">single_pair_short_path / 6</A>, <A HREF="../../lib/graph_algorithms/graph_get_incoming_edges-3.html">graph_get_incoming_edges / 3</A>, <A HREF="../../lib/graph_algorithms/graph_set_nodenames-2.html">graph_set_nodenames / 2</A>
</BODY></HTML>
